package euler;


import java.math.*;
import java.util.ArrayList;
import java.util.HashMap;
import static java.lang.Math.*;

public class Problems {

	/**
	 * @param args
	 */
	public static void main(String[] args) {		
		solveMultiplesOf3And5();
		//evenFibonacciNumbers();		
		//largestPalindrome();
		
		//System.out.println("divisibleBy(1,10)="+divisibleBy(1,10));
		//System.out.println("divisibleBy(1,20)="+divisibleBy(1,20));
		//long zwanzig=16*17*19*5*13*11*7*9;System.out.println(zwanzig);		
		//System.out.println("largestProduct()="+largestProduct());
		//findTriplet();
		//System.out.println(squareOfSums(100));
		//System.out.println(numberOfRountes(20));
		//System.out.println(letterCount());
		//System.out.println(collatzNo(113383));
		//System.out.println(largestCollatz(1000000));
		
		//System.out.println(triangleNumber(7));
		//System.out.println(firstHighTriDivNumber(100));
		
		//System.out.println("sumOfDivisors="+calcSumOfDivisors(12));
		//ArrayList<Integer> abNoList = listAbundantNumbers(28123);
		//System.out.println("abNoList.size="+abNoList.size());
		//sumsOfTwo(abNoList);
		//System.out.println(abSumsFound.toString());
		//System.out.println("abNoList summed");
		//long sum=listNotInAbSumsFound(30123);
		//System.out.println("sum of non-sum-producable="+sum);		
		//System.out.println("FibonacciIterations="+bigFibonacci(1000));
		//System.out.println("sumOfAmicableNumbers="+listOfAmicableNumbers(10000));
	}
	
	public static long bigFibonacci(int limit) {
		
		BigInteger fn1 = BigInteger.valueOf(1);
		BigInteger fn2 = BigInteger.valueOf(1);
		BigInteger fn;
		
		long noOfDigits=0;
		int iteration=2;
		
		while (noOfDigits<limit) {
			fn=fn1.add(fn2);
			String fnStr=fn.toString(10);			
			noOfDigits=fnStr.length();
			fn1=fn2;
			fn2=fn;
			iteration++;
		}
		return iteration;
	}
	
	public static long numberOfCoinVariations(ArrayList<Integer> coinsize, int maxCoin, int pennySum) {
		long variationSum=0;
		
		for (int coinIdx=coinsize.size()-1;coinIdx>=0;coinIdx--) {
			int currCoinSize=coinsize.get(coinIdx);
			
			if (currCoinSize<=pennySum) {
				int reducedAmount=pennySum;				
				while (reducedAmount>0) {
				  reducedAmount=reducedAmount-currCoinSize;
				  if (reducedAmount==0) variationSum++;
				  else variationSum=variationSum+numberOfCoinVariations(coinsize,currCoinSize,reducedAmount);
				}
			}
		}
		
		return variationSum;
	}
	
	public static long sumArr(ArrayList<Long> list2sum) {
		long sum=0;
		for (int i=0;i<list2sum.size();i++) sum=sum+list2sum.get(i);
		return sum;
	}
	
	public static ArrayList<Long> createTestArrayList(int listSize) {
		ArrayList<Long> testArr = new ArrayList<Long>();
		for (long i=0;i<listSize;i++)
			testArr.add(i+i);
		return testArr;
	}
	
	public static long largestPrimeFactor(long testFactors) {
		
		long largestPrime=1;
		long primeLimit=round(sqrt((double)testFactors+2));
		ArrayList<Long> primes = calcPrimelist((int)primeLimit,-1);
		//long testFactors=Long.parseLong("600851475143");
		for (int  primeIdx=0;
				   primeIdx<primes.size() 		
		        && primes.get(primeIdx)<primeLimit;				
			       primeIdx++) {
			long prime4test=primes.get(primeIdx);
			if ((testFactors % prime4test==0) && (prime4test>largestPrime)) {
				//System.out.println("primefactor:"+primes.get(primeIdx));
				largestPrime=prime4test;				
			}
		}
		return largestPrime;		
	}
	
	public static long calcNthPrimeNumber(int n) {
		ArrayList<Long> primes =calcPrimelist(-1,n-1);
		return primes.get(primes.size()-1);
	}
	
	public static String largeUnitFraction(int divisorInt) {
			BigDecimal divisor = new BigDecimal(""+divisorInt);
			BigDecimal one = new BigDecimal("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
			BigDecimal division= one.divideToIntegralValue(divisor);
		return division.toString();
	}
	
	public static String findWiederholung(String seqStr) {
		
		HashMap<String,Integer> seqMap = new HashMap<String,Integer>();		
		int maxLength=0;
		int firstPos=-1;
		int secondPos=-1;
		String maxSequence="";
		for (int seqBeginIdx=0;seqBeginIdx<seqStr.length()-2;seqBeginIdx++) {
			for (int seqEndIdx=seqBeginIdx+1;seqEndIdx<seqStr.length();seqEndIdx++) {
				String subSeq=seqStr.substring(seqBeginIdx,seqEndIdx);
				if (seqMap.get(subSeq)==null)seqMap.put(subSeq, 1);	
				else seqMap.put(subSeq, seqMap.get(subSeq)+1);
			}
		}		
		
		for (String key : seqMap.keySet()) {
			if (seqMap.get(key)>1 && key.length()>maxLength) {
				maxSequence=key;
				maxLength=key.length();
			}
		}
		
		firstPos=seqStr.indexOf(maxSequence);
		secondPos=seqStr.indexOf(maxSequence, firstPos+1);		
		if (maxSequence.length()>secondPos-firstPos) {
			maxSequence=seqStr.substring(firstPos,secondPos);
		}
		System.out.println("Seqence="+maxSequence+"@"+firstPos+" "+secondPos);
		
		return maxSequence;
	}
	
	public static long prob421_s(long n, long m) {
		long sum=0;
		//BigInteger nBig= BigInteger.valueOf(n);
		//BigInteger nRaised15 = nBig.pow(15);
		//BigInteger nRaised15plusOne = nRaised15.add(BigInteger.valueOf(1));
		
		return sum;
	}
	
	public static ArrayList<Long> distinctPrimefactors(long n) {
		return distinctPrimefactorsNotExceedingM(n, n);
	}
	
	public static ArrayList<Long> distinctPrimefactorsNotExceedingM(long n, long m) {
		ArrayList<Long> distinctList = new ArrayList<Long>();
		
		ArrayList<Long> primes = calcPrimelist((int)min(n,m),-1);
		
		for (int primeIdx=0;primeIdx<primes.size() && primes.get(primeIdx)<=m;primeIdx++) {
			if (n % primes.get(primeIdx)==0) distinctList.add(primes.get(primeIdx));
		}
		if (distinctList.size()==0) distinctList.add(n);
		
		return distinctList;
	}
	
	public static ArrayList<Long> calcPrimelist(long primeUpperLimit,int listLimit) {
		ArrayList<Long> primes = new ArrayList<Long>();
		
		for (long zahl=2;				   
				   condCheckSmaller((int)zahl,primeUpperLimit)
				&& condCheckSmallerEqual(primes.size(),listLimit); 
				   zahl++) {
			boolean divisible=false;
									
			for (int primeIdx=0;
						primeIdx<primes.size() 
						&& !divisible 
						&& primes.get(primeIdx)<Math.sqrt((double)zahl)+1;
						primeIdx++) {
				if (zahl % primes.get(primeIdx)==0) {
					     divisible=true;
				}				
			}
			if (!divisible) primes.add(zahl);	
		}	
		
		return primes;
	}
	
	public static boolean condCheckSmaller(int currListSize, long listLimit) {
		return (listLimit<0 || currListSize<listLimit);
	}
	
	public static boolean condCheckSmallerEqual(int currListSize, int listLimit) {
		return (listLimit<0 || currListSize<=listLimit);
	}
	
	public static long firstHighTriDivNumber(int numberOfDivsLimit) {
		long currTriNumber=triangleNumber(2);
		long counter=2;
		while (numberOfProperDivisors(currTriNumber)<numberOfDivsLimit) {
			counter++;
			currTriNumber=triangleNumber(counter);
		}
		return currTriNumber;
	}
			
	public static long listOfAmicableNumbers(long limit) {
		long sum=0;		
		for (long i=1;i<limit;i++) {
			long di=sumOfProperDivisors(i);
			if (sumOfProperDivisors(di)==i && di!=i) {
				System.out.println(i+"<->"+di);				
				sum=sum+di+i;
			}
		}
		return sum/2;
	}
	
	public static long numberOfProperDivisors(long num2Check) {
		
		int numOfDivs=0;
		for (int i=1;i<num2Check/2+1;i++) 
			if ((num2Check % i)==0) numOfDivs++;
		return numOfDivs;
	}
			
    public static long sumOfProperDivisors(long num2Check) {
		
		long sumOfDivs=0;
		long num2calcdHalf = num2Check/2+1;
		for (int i=1;i<num2calcdHalf;i++) 
			if ((num2Check % i)==0) sumOfDivs=sumOfDivs+i;
		return sumOfDivs;
	}
	
	public static long triangleNumber(long n) {
		long triNum=0;
		for (int i=1;i<=n;i++) triNum=triNum+i;
		return triNum;
	}
	
	public static HashMap<Integer,String> abSumsFound = new HashMap<Integer,String>();
	
	public static long listNotInAbSumsFound(int limit) {
		long sum=0;
		for (int i=1;i<=limit;i++)
			if (abSumsFound.get(i)==null) {
				//System.out.println(i+",");
				sum=sum+i;
			}
		return sum;
	}
	
	public static void sumsOfTwo(ArrayList<Integer> noList) {
		int sum;
		for (int rowIdx=0;rowIdx<noList.size();rowIdx++)
			for (int colIdx=0;colIdx<noList.size();colIdx++) {
				sum=noList.get(rowIdx)+noList.get(colIdx);
				if (abSumsFound.get(sum)==null) abSumsFound.put(sum, "1");
			}
	}
	
	public static ArrayList<Integer>   listAbundantNumbers(int limit) {
		ArrayList<Integer> abundantNoList = new ArrayList<Integer>();
		for (int i=1;i<=limit;i++)
			if (isAbundantNumber(i)) abundantNoList.add(i);
		return abundantNoList;
	}
	
	public static boolean isAbundantNumber(int num2calcd) {
		return (sumOfProperDivisors(num2calcd)>num2calcd);
	}
	
	
	
	public static long largeTriangle() {
		
		
		return -1;
	}
	
	public static long numberOfRountes(int meshsize) {
		long prod=1;
		for (int idx=1;idx<=meshsize;idx++) {
			prod=prod*(2*idx)*(2*idx-1);
			prod=prod/(idx*idx);
		}
		
		return prod;
	}
	
	static HashMap<Integer,Integer> collNo = new HashMap<Integer,Integer>();
	
	public static long largestCollatz(int upTo) {
		long maxCol=0;
		
		for (int colIdx=2;colIdx<upTo;colIdx++) {
			//if ((colIdx % 10000)==0) System.out.println(colIdx);
			long colNo=collatzNo(colIdx);
			if (colNo>maxCol) {
				maxCol=colNo;
				System.out.println("new max @"+colIdx+" value="+colNo);
			}
		}
		return maxCol;
	}
	
	public static long collatzNo(int n) {
		int count=1;
		long seqNo=n;
		collNo.put(1, 1);
		if (!collNo.containsKey(n)) {
			while (seqNo!=1) {
				if (collNo.containsKey(seqNo)) {
					count=count+collNo.get(seqNo);
					seqNo=1;
				} else {
					if ((seqNo%2)==0) seqNo=seqNo/2;
					else              seqNo=3*seqNo+1;					
					count++;
				}
			}
			collNo.put(n,count);
		} else {
			count=collNo.get(n);
		}		
		return count;
	}
	
	public static long letterCount() {
		
		HashMap<Integer,String> zehner = new HashMap<Integer,String>();
		
		HashMap<Integer,String> hunderter = new HashMap<Integer,String>();
		
				
		hunderter.put(1, "one hundred");		
		hunderter.put(2, "two hundred");
		hunderter.put(3, "three hundred");
		hunderter.put(4, "four hundred");
		hunderter.put(5, "five hundred");
		hunderter.put(6, "six hundred");
		hunderter.put(7, "seven hundred");
		hunderter.put(8, "eight hundred");
		hunderter.put(9, "nine hundred");
		
		zehner.put(2, "twenty");
		zehner.put(3, "thirty");
		zehner.put(4, "fourty");
		zehner.put(5, "fifty");
		zehner.put(6, "sixty");
		zehner.put(7, "seventy");
		zehner.put(8, "eighty");
		zehner.put(9, "ninety");
		
		
		
		String letters="one two three four five six seven eight nine ten eleven twelve" +
				"thirteen fourteen fifteen sixteen seventeen eighteen nineteen"
		;
		/*
		for (int zaehler=1;zaehler<1000;zaehler++) {
			if (zaehler<100) {
				int zehnerZiffer=(zaehler-zaehler%10)/10;
				int einerZiffer=zaehler-(zehnerZiffer*10);
				System.out.println(zehner.get(zehnerZiffer)+" "+einer.get(einerZiffer));
			} else {
				int hunderterZiffer=(zaehler-zaehler%100)/100;
				int zehnerZiffer=(zaehler-hunderterZiffer-zaehler%10)/10;
				int einerZiffer=zaehler-hunderterZiffer-(zehnerZiffer*10);
				String and="";
				if (zehnerZiffer>0 && einerZiffer>0) {
					and="and";
				}
				System.out.println(hunderter.get(hunderterZiffer)+" "zehnerZiffer);
			}
		}*/
	
		
		letters.replaceAll(" ", "");
		return letters.length();
	}
	
	public static String numbers2nineteen(int number) {
		HashMap<Integer,String> einer = new HashMap<Integer,String>();
		einer.put(1, "one");		
		einer.put(2, "two");
		einer.put(3, "three");
		einer.put(4, "four");
		einer.put(5, "five");
		einer.put(6, "six");
		einer.put(7, "seven");
		einer.put(8, "eight");
		einer.put(9, "nine");
		einer.put(10, "ten");
		einer.put(11, "eleven");
		einer.put(12, "twelve");
		einer.put(13, "thirteen");
		einer.put(14, "fourteen");
		einer.put(15, "fifteen");
		einer.put(16, "sixteen");
		einer.put(17, "seventeen");
		einer.put(18, "eighteen");
		einer.put(19, "nineteen");
		return einer.get(number);
	}
	public static long faculty(int n) {
		long prod=1;
		for (int idx=1;idx<=n;idx++)
			prod=prod*idx;
		return prod;
	}
	
	public static long solveMultiplesOf3And5() {
		long sum=0;
		for (long zahl=1;zahl<1000; zahl++) {			
			if ((zahl % 5)==0 || (zahl % 3)==0) sum=sum+zahl;
		}
		System.out.println(sum);
		return sum;
	}
	
	public static int findTriplet() {
		
		int schranke=800;
		int prod=-1;
		for (int a=1;a<schranke;a++)
			for (int b=1;b<schranke;b++)
				for (int c=1;c<schranke;c++)
					if (isPythagorean(a,b,c) && ((a+b+c)==1000)) {
						//System.out.println("a="+a+" b="+b+" c="+c);
						prod=a*b*c;
						//System.out.println("prod="+prod);
					}
		return prod;
	}
	
	public static boolean isPythagorean(int a, int b, int c) {
		return a*a+b*b==c*c;
	}
	
	public static long divisibleBy(int von, int bis) {
		long kgV=0;
		boolean hasRemainder=true;
		
		while (hasRemainder) {
			kgV++;
			boolean remainderFound=false;
			for (int testInt=von;testInt<=bis && !remainderFound;testInt++)
				if ((kgV % testInt)!=0) remainderFound=true;
			hasRemainder=remainderFound;
		}
		return kgV;
	}
	
	public static long evenFibonacciNumbers() {		
		long f1=1;
		long f2=2;
		long f3=f1+f2;
		long sum=2;
		
		long fourMillion=4*1000*1000;
		while (f3<fourMillion) {
			if ((f3%2)==0) sum=sum+f3;
			f1=f2;
			f2=f3;			
			f3=f1+f2;
		}
		System.out.println(sum);
		return sum;
		
	}
	
	public static long largestProduct() {
	    long largestProduct=0;	                  
		String testStr=  "73167176531330624919225119674426574742355349194934" +
				         "96983520312774506326239578318016984801869478851843" +
				         "85861560789112949495459501737958331952853208805511" +
				         "12540698747158523863050715693290963295227443043557" +
				         "66896648950445244523161731856403098711121722383113" +
				         "62229893423380308135336276614282806444486645238749" +
				         "30358907296290491560440772390713810515859307960866" +
				         "70172427121883998797908792274921901699720888093776" +
				         "65727333001053367881220235421809751254540594752243" +
				         "52584907711670556013604839586446706324415722155397" +
				         "53697817977846174064955149290862569321978468622482" +
				         "83972241375657056057490261407972968652414535100474" +
				         "82166370484403199890008895243450658541227588666881" +
				         "16427171479924442928230863465674813919123162824586" +
				         "17866458359124566529476545682848912883142607690042" +
				         "24219022671055626321111109370544217506941658960408" +
				         "07198403850962455444362981230987879927244284909188" +
				         "84580156166097919133875499200524063689912560717606" +
				         "05886116467109405077541002256983155200055935729725" +
				         "71636269561882670428252483600823257530420752963450";
	
		for (int laufIdx=0;laufIdx<testStr.length()-5;laufIdx++) {
			
			long product=getProduct(laufIdx,testStr,5);
			if (product>largestProduct) largestProduct=product;
		}
		
	return largestProduct;		
	}
	
	public static long getProduct(int posIdx, String testStr, int anz) {
		long prod=1;
		for (int laufIdx=posIdx;laufIdx<posIdx+anz;laufIdx++) 
			prod=prod*Integer.parseInt(testStr.substring(laufIdx,laufIdx+1));
		return prod;
	}
	
	public static long largestPalindrome() {
		
		long largestPalindrome=0;
		for (int firstIdx=100;firstIdx<999;firstIdx++) 
			for (int secondIdx=100;secondIdx<999;secondIdx++) {
				long product=firstIdx*secondIdx;
				if (isPalindrome(product) && product>largestPalindrome) largestPalindrome=product;
			}		
		System.out.println("largestPalindrome="+largestPalindrome);	
		return largestPalindrome;
	}
	
	public static boolean isPalindrome(long testnumber) {
				
		String testNumberStr=""+testnumber;
		String reverseStr="";
		for (int strIdx=testNumberStr.length()-1;strIdx>=0;strIdx--) {
			reverseStr=reverseStr+testNumberStr.substring(strIdx, strIdx+1);
		}
		return reverseStr.equalsIgnoreCase(testNumberStr);
	}
	
	public static long squareOfSums(int maximum) {
		long square_sum=0;
		long idx_sum=0;
		for (int idx=1;idx<=maximum;idx++) {
			square_sum=square_sum+idx*idx;
			idx_sum=idx_sum+idx;
		}
		return idx_sum*idx_sum-square_sum;
	}

}
